/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number[]}
 */
export var findMinHeightTrees = function (n, edges) {
  const map = new Map() // 记录每个节点与之相连的各个节点
  let nodes = new Array(n).fill(0).map((_, i) => i)
  if (n < 1) {
    return []
  }
  if (n === 1) {
    return [0]
  }
  if (n === 2) {
    return [0, 1]
  }
  for (const edge of edges) {
    const [node1, node2] = edge
    pushNodeToMap(map, node1, node2)
    pushNodeToMap(map, node2, node1)
  }
  return bfs(nodes, map, 0)
}

function pushNodeToMap(map, node1, node2) {
  if (map.has(node1)) {
    map.get(node1).push(node2)
  } else {
    map.set(node1, [node2])
  }
}

function bfs(nodes, map) {
  if (nodes.length < 3) {
    return nodes
  }
  const newNodes = []
  const targetDeleteNodes = {}
  for (const nodeName of nodes) {
    if (map.get(nodeName).length === 1) {
      const targetNode = map.get(nodeName)[0]
      targetDeleteNodes[targetNode] = targetDeleteNodes[targetNode] || []
      targetDeleteNodes[targetNode].push(nodeName)
      map.delete(nodeName)
    } else {
      newNodes.push(nodeName)
    }
  }
  // 删除map中对应的子节点
  for (const targetNode in targetDeleteNodes) {
    const deleteNodes = targetDeleteNodes[targetNode]
    map.set(
      Number(targetNode),
      map.get(Number(targetNode)).filter(node => !deleteNodes.includes(node))
    )
  }
  return bfs(newNodes, map)
}
